package twice.class_digui;
//最长公共子序列
public class Class09_LongestCommonSubsequence {
    public static int longestCommonSubsequence1(String s1, String s2){
        if (s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0) {
            return 0;
        }
        char[] a = s1.toCharArray();
        char[] b = s2.toCharArray();
        return process1(a,b,s1.length()-1,s2.length()-1);
    }

    public static int process1(char[] str1,char[] str2,int i,int j){
        if(i == 0 && j == 0){
            return str1[i] == str2[i] ? 1:0;
        }

        if(i == 0){
            if (str1[i] == str2[j]) {
                return 1;
            } else {
                return process1(str1, str2, i, j - 1);
            }
        }

        if(j == 0){
            if (str1[i] == str2[j]) {
                return 1;
            } else {
                return process1(str1, str2, i-1, j);
            }
        }


        int p1 = process1(str1, str2, i-1, j);
        int p2 = process1(str1, str2, i, j-1);
        int p3 = str1[i] == str2[j] ? (1 + process1(str1, str2, i - 1, j - 1)) : 0;
        return Math.max(p1, Math.max(p2, p3));
    }

    public static int longestCommonSubsequence2(String s1, String s2){
        if (s1 == null || s2 == null || s1.length() == 0 || s2.length() == 0) {
            return 0;
        }
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        int[][] dp = new int[s1.length()][s2.length()];
        dp[0][0] = str1[0] == str2[0] ? 1:0;

        for(int i = 0; i < dp.length;i++){
            dp[i][0] = str1[i] == str2[0] ? 1 : dp[i - 1][0];
        }
        for(int i = 0; i < dp[0].length;i++){
            dp[0][i] = str1[0] == str2[i] ? 1 : dp[0][i - 1];
        }
        for(int i = 1; i < dp.length;i++){
            for (int j = 1; j < dp[0].length; j++) {
                dp[i][j] = Math.max(dp[i-1][j], Math.max(dp[i][j-1], str1[i] == str2[j] ? (1 + dp[i - 1][j - 1]) : 0));
            }
        }
        return dp[dp.length-1][dp[0].length-1];
    }
}
